package leetcode.Hot100;

import leetcode.tencent.threeSumClosest;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

/**
 * @author Cheng Jun
 * Description: 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，
 * 使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
 * <p>
 * 注意：答案中不可以包含重复的三元组。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/3sum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @version 1.0
 * @date 2021/11/30 10:48
 * @see threeSumClosest
 */
public class threeSum {
    public static void main(String[] args) {
        System.out.println(threeSum(new int[]{0, 0, 0, 0, 0}));
        System.out.println(threeSum1(new int[]{0, 0, 0, 0, 0}));
    }

    // 输入：nums = [-1,0,1,2,-1,-4]
    // 输出：[[-1,-1,2],[-1,0,1]]
    // 三数之和 为0，其实就是 两数之和 为 -c， a+b= -c
    // c 为 nums 中每一个数，条件限制答案不可有重复的三元组，意思是 如果nums 为（-1,-1,0,1,）只能返回 -1,0,1
    public static List<List<Integer>> threeSum(int[] nums) {
        // 排序，避免相同数字的计算
        Arrays.sort(nums);
        List<List<Integer>> resultList = new ArrayList<>();
        if (nums.length < 3) return resultList;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) break;
            // 如果 nums[i] 等于 nums[i-1]，跳过
            if (i != 0 && nums[i - 1] == nums[i]) continue;
            // 两数之和
            int target = -nums[i];
            // key 为 target - nums[j], value 为 j
            HashMap<Integer, Integer> diffMap = new HashMap<>();
            for (int j = i + 1; j < nums.length; j++) {
                int diff = target - nums[j];
                if (diffMap.containsKey(diff)) {
                    List<Integer> threeSumList = new ArrayList<>();
                    threeSumList.add(nums[i]);
                    threeSumList.add(nums[j]);
                    if (diffMap.get(diff) != -1) {
                        threeSumList.add(nums[diffMap.get(diff)]);
                        resultList.add(threeSumList);
                    }
                    // 表示 该差值 已经被用过
                    diffMap.put(diff, -1);
                } else {
                    diffMap.put(nums[j], j);
                }
            }
        }
        return resultList;
    }

    // 双指针
    public static List<List<Integer>> threeSum1(int[] nums) {
        // 排序，避免相同数字的计算
        Arrays.sort(nums);
        List<List<Integer>> resultList = new ArrayList<>();
        if (nums.length < 3) return resultList;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) break;
            // 如果 nums[i] 等于 nums[i-1]，跳过
            if (i != 0 && nums[i - 1] == nums[i]) continue;
            // 两数之和
            int target = -nums[i];
            int left = i + 1;
            int right = nums.length - 1;
            while (left < right) {
                if (nums[left] + nums[right] > target) {
                    right--;
                } else if (nums[left] + nums[right] < target) {
                    left++;
                } else {
                    List<Integer> targetList = new ArrayList<>();
                    targetList.add(nums[left]);
                    targetList.add(nums[right]);
                    targetList.add(nums[i]);
                    resultList.add(targetList);
                    // -2 -1 0 2 3
                    // 右移left 跳过重复值
                    while (left < right && nums[left] == nums[++left]) ;
                    // 左移 right 跳过重复值
                    while (left < right && nums[right] == nums[--right]) ;
                }
            }
        }
        return resultList;
    }

}
